﻿// 1125. 最小的必要团队.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <map>


using namespace std;
/*
https://leetcode.cn/problems/smallest-sufficient-team/

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」
（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。
可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

示例 1：
输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]

示例 2：
输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], 
people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
输出：[1,2]


提示：

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] 由小写英文字母组成
req_skills 中的所有字符串 互不相同
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] 由小写英文字母组成
people[i] 中的所有字符串 互不相同
people[i] 中的每个技能是 req_skills 中的技能
题目数据保证「必要团队」一定存在
*/


class Solution {
public:
    vector<vector<int>> dp;
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        map<string, int> mm; int idx = 0;
        for (auto& e : req_skills) {
            mm[e] = idx++;
        }

        dp.resize(1<< req_skills.size(), vector<int>(people.size()+5, 0x3f3f3f3f));
        //memset(dp,0x3f,sizeof dp);
        dp[0][0] = 0;
        int allSkil = (1 << mm.size())-1;
        people.insert(people.begin(), vector<string>());

        vector<int> gi(1 << req_skills.size()), gm(1 << req_skills.size());

        for (int i = 1; i < people.size(); i++) {
            int currSkil = 0;
            for (int j = 0; j < people[i].size(); j++) {
                string name = people[i][j];
                currSkil |= (1 << mm[name]);
            }

            for (int state = 0; state < (1 << req_skills.size()); state++) {
                //不选
                dp[state][i] = min(dp[state][i], dp[state][i - 1]);

                if (dp[state][i] > dp[state & (~currSkil)][i - 1] + 1) {
                    dp[state][i] = dp[state & (~currSkil)][i - 1] + 1;
                    gi[state] = i;
                    gm[state] = state & (~currSkil);
                }
            }
        }
       
        vector<int> ans;
        for (int mask = allSkil; mask > 0; mask = gm[mask]) {
            ans.push_back(gi[mask]-1);
        }

        return  ans;
    }
};


int main()
{
    Solution s;
    vector<string> skill = {
        "java", "nodejs", "reactjs"
    };

    vector<vector<string>> p = {
        {"java"} ,{"nodejs"},{"nodejs", "reactjs"}
    };
    
    s.smallestSufficientTeam(skill,p);
}

 